# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 21/50 最长等差数列
# leetcode第1027题: https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
# Date: 2024/11/11
from functools import cache

from leetcode import test


def longestArithSeqLength(nums: list[int]) -> int:
    """暴力算法求解, 在leetcode中超时"""
    n = len(nums)
    max_len = 0
    for i in range(n):
        if i >= n - max_len:
            return max_len
        for j in range(i + 1, n):
            dif = nums[j] - nums[i]  # 计算差值
            cnt, v, flag = 2, float('inf'), True
            result = [{i: nums[i]}, {j: nums[j]}]  # 一个用于debug的变量, 可以检查所有符合条件的等差数列
            for k in range(j + 1, n):
                if dif == nums[k] - nums[j] and flag:
                    cnt = cnt + 1
                    v = nums[k]
                    flag = False
                    result.append({k: nums[k]})
                    continue
                if dif == nums[k] - v:
                    cnt = cnt + 1
                    v = nums[k]
                    result.append({k: nums[k]})
            max_len = max(max_len, cnt)

    return max_len


def longestArithSeqLength_dp(nums: list[int]) -> int:
    """使用动态规划的方法求解
    记dp[i][d][num]为使用数组nums中下标在小于等于i的元素, 构造公差为d的等差数列, 并且最后一个元素为num时, 等差数列长度的最大值
    在进行状态转移的时候, 我们只需要考虑是否将当前第i个元素作为末项加入等差数列:
    1> 如果不加入等差数列, 状态转移方程为 dp[i][d][num] = dp[i-1][d][num]
    2> 如果加入等差数列,那么分为两种情况:
        1> 此时等差数列的长度大于等2, 末项为nums[i], 那么倒数第二项的值为nums[i]-d, 状态转移方程为
        dp[i][d][nums[i]] = dp[i-1][d][nums[i]-d] + 1
        2> 若等差数列的长度为1, 即 nums[i]单独为一个数列的初始情况: dp[i][d][nums[i]] = 1
    最终的答案就是dp数组中的最大值, 需要注意的是，d 的取值范围是 [−diff,diff]，其中 diff 是数组 nums 中最大值与最小值的差。
    如何优化上述方法?
    可以看到当dp的第一维从 i-1 变为 i 之后, 实际上只有dp[i][d][nums[i]]可能会相对于dp[i-1][d][nums[i]]发生变化, 其余的值均保持不变.
    因此, 可以省去第一维,在状态转移的时候只需要修改最多一个状态的值.
    此时，状态变为 f[d][num]，当我们遍历到数组 nums 的第 i 个元素时，只需要进行两种情况:
    dp[d][nums[i]] = dp[d][nums[i]−d] + 1
    dp[d][nums[i]] = 1
    又由于dp[d][..]只能从dp[d][..]转移过来, 所以我们进一步去掉当前的第一维, 使用一个外层循环枚举 d，而在内层循环中，只需要进行:
    dp[nums[i]] = dp[nums[i] - d] + 1
    dp[nums[i]] = 1
    """
    minv, maxv = min(nums), max(nums)
    max_dif = maxv - minv
    max_len = 1  # 最小为1

    for d in range(-max_dif, max_dif + 1):
        dp = dict()
        for num in nums:
            if (prev := num - d) in dp:  # := 为海象运算符, 也就是将prev定义为 num - d 的意思
                dp[num] = max(dp.get(num, 0), dp[prev] + 1)  # dp.get(num, 0)表示获取键为num时如果为空, 则返回0而不是None
                max_len = max(max_len, dp[num])
            dp[num] = max(dp.get(num, 0), 1)

    return max_len


def longestArithSeqLength_dfs(nums: list[int]) -> int:
    @cache  # 缓存装饰器，避免重复计算 dfs 的结果
    def dfs(i: int) -> dict[int, int]:
        """对数组中的每个元素进行深度"""
        # i=0 时不会进入循环，返回空哈希表
        max_len = {}
        for j in range(i - 1, -1, -1):
            d = nums[i] - nums[j]  # 公差
            if d not in max_len:
                max_len[d] = dfs(j).get(d, 1) + 1
        return max_len

    return max(max(dfs(i).values()) for i in range(1, len(nums)))


if __name__ == '__main__':
    n0 = [1, 2]
    n1 = [3, 6, 9, 12]
    n2 = [9, 4, 7, 2, 10]
    n3 = [20, 1, 15, 3, 10, 5, 8]
    n4 = [83, 20, 17, 43, 52, 78, 68, 45]
    n5 = [12, 28, 13, 6, 34, 36, 53, 24, 29, 2, 23, 0, 22, 25, 53, 34, 23, 50, 35, 43, 53, 11, 48, 56, 44, 53, 31, 6,
          31, 57, 46, 6, 17, 42, 48, 28, 5, 24, 0, 14, 43, 12, 21, 6, 30, 37, 16, 56, 19, 45, 51, 10, 22, 38, 39, 23, 8,
          29, 60, 18]
    n6 = [44, 46, 22, 68, 45, 66, 43, 9, 37, 30, 50, 67, 32, 47, 44, 11, 15, 4, 11, 6, 20, 64, 54, 54, 61, 63, 23, 43,
          3, 12, 51, 61, 16, 57, 14, 12, 55, 17, 18, 25, 19, 28, 45, 56, 29, 39, 52, 8, 1, 21, 17, 21, 23, 70, 51, 61,
          21, 52, 25, 28]
    n7 = [0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1,
          0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
          1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0,
          0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
          0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1,
          1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1,
          0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1,
          0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0,
          0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1,
          1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
          0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
          0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0,
          1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0,
          0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0,
          1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1,
          0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0,
          0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1,
          0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1,
          1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1,
          1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0,
          0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0,
          0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1]
    inp = [{"nums": n0}, {"nums": n1}, {"nums": n2}, {"nums": n3}, {"nums": n4}, {"nums": n5}, {"nums": n6},
           {"nums": n7}, ]
    out = [2, 4, 3, 4, 2, 4, 6, 416]
    test.test_function(longestArithSeqLength, inp, out)
    test.test_function(longestArithSeqLength_dp, inp, out)
    test.test_function(longestArithSeqLength_dfs, inp, out)
